package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname MaximumProductSubarray
 * @Description Leetcode 152. 乘积最大子数组 中等难度 动态规划
 * @Date 2021/10/12 20:39
 * @Version 1.0
 */
public class MaximumProductSubarray {
    /**
     * 全局最优解并不依赖与全局的最优解
     *
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {

        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int result = Integer.MIN_VALUE;
        if (len == 1) {
            return nums[0];
        }
        //维护一个最大最小数组 用于保存当前的最大最小序列，
        int[] maxArr = new int[len];
        int[] minArr = new int[len];
        minArr[0] = nums[0];
        maxArr[0] = nums[0];

        result = maxArr[0];
        for (int i = 1; i < len; i++) {

            int tmp = nums[i];
            //分正负数讨论，
            maxArr[i] = Math.max(tmp, Math.max(minArr[i - 1] * tmp, maxArr[i - 1] * tmp));
            minArr[i] = Math.min(tmp, Math.min(minArr[i - 1] * tmp, maxArr[i - 1] * tmp));
            result = Math.max(result, maxArr[i]);
        }
        return result;
    }

    /**
     * 滚动数组 空间优化 不同于Leetcode 53 最大子序列
     *
     * @param nums
     * @return
     */
    public int maxProduct1(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
//        int result = Integer.MIN_VALUE;
        if (len == 1) {
            return nums[0];
        }
        //维护一个最大最小数组 用于保存当前的最大最小序列，

        int minArr = nums[0];
        int maxArr = nums[0];

        int result = maxArr;

        for (int i = 1; i < len; i++) {

            int num = nums[i];
            int m1 = maxArr;
            int m2 = minArr;

            maxArr = Math.max(num, Math.max(m2 * num, m1 * num));
            minArr = Math.min(num, Math.min(m2 * num, m1 * num));

            result = Math.max(result, maxArr);
        }

        return result;
    }
}
